#leetcode题目994：腐烂的橘子
#难度：中等
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：BFS ，传染法

from typing import List
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        """
        腐烂的橘子
        在给定的网格中，每个单元格可以有以下三个值之一：
        - 值 0 代表空单元格；
        - 值 1 代表新鲜橘子；
        - 值 2 代表腐烂的橘子。
        每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
        返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
        """
        m = len(grid)
        n = len(grid[0])
        step = 0
        count = self.count(grid)  # 统计新鲜橘子数量
        last_count = -1
        
        while count > 0:
            # 如果新鲜橘子数量没有变化，说明无法继续腐烂
            if last_count == count:
                return -1
            
            step += 1
            
            # 遍历所有腐烂的橘子，感染相邻的新鲜橘子
            for y in range(m):
                for x in range(n):
                    if grid[y][x] == 2:
                        self.infect(grid, x, y)
            
            last_count = count
            count = count - self.flash(grid)  # 更新新鲜橘子数量，新鲜橘子数量-本轮腐烂的橘子数量=本轮之后的新鲜橘子数量
            #也就是count为0的时候，说明没有新鲜橘子了，也就是腐烂完了。
        
        return step

    def flash(self, grid: List[List[int]]) -> int:
        """
        刷新函数：将标记为即将腐烂的橘子变为腐烂状态
        :param grid: 二维网格
        :return: 本轮腐烂的橘子数量
        """
        m = len(grid)
        n = len(grid[0])
        count = 0
        
        # 遍历网格，将标记为-2的橘子变为腐烂状态
        for y in range(m):
            for x in range(n):
                if grid[y][x] == -2:
                    count += 1
                    grid[y][x] = 2  # 变为腐烂状态
        
        return count

    def infect(self, grid: List[List[int]], x: int, y: int) -> None:
        """
        感染函数：将相邻的新鲜橘子标记为即将腐烂
        :param grid: 二维网格
        :param x: 列坐标
        :param y: 行坐标
        """
        m = len(grid)
        n = len(grid[0])
        
        # 边界检查
        if x < 0 or x >= n:
            return
        if y < 0 or y >= m:
            return
        if grid[y][x]==2: #如果当前格子是腐烂的橘子，则标记相邻的新鲜橘子
            self.mark(grid, x + 1, y)  # 右
            self.mark(grid, x - 1, y)  # 左
            self.mark(grid, x, y + 1)  # 下
            self.mark(grid, x, y - 1)  # 上

    def mark(self, grid: List[List[int]], x: int, y: int) -> None:
        """
        标记函数：将指定位置的新鲜橘子标记为即将腐烂
        :param grid: 二维网格
        :param x: 列坐标
        :param y: 行坐标
        """
        m = len(grid)
        n = len(grid[0])
        
        # 边界检查
        if x < 0 or x >= n:
            return
        if y < 0 or y >= m:
            return
        
        # 如果当前格子是新鲜橘子，标记为即将腐烂
        if grid[y][x] == 1:
            grid[y][x] = -2  # 标记为即将腐烂状态
    

    def count(self, grid: List[List[int]]) -> int:
        """
        统计新鲜橘子数量
        :param grid: 二维网格
        :return: 新鲜橘子数量
        """
        m = len(grid)
        n = len(grid[0])
        count = 0
        
        for y in range(m):
            for x in range(n):
                if grid[y][x] == 1:
                    count += 1
        
        return count


#测试数据
grid = [
    [2,1,1],
    [1,1,0],
    [0,1,1]
] #这里的2代表腐烂的橘子，1代表新鲜橘子，0代表空单元格，即没有橘子。
#预期输出：4
solution = Solution()
print(solution.orangesRotting(grid))



grid = [
    [2,1,1],
    [0,1,1],
    [1,0,1]
]
#预期输出：-1，左下角的橘子永远无法腐烂，因此返回-1
solution = Solution()
print(solution.orangesRotting(grid))


grid = [
    [0,2]
]
#预期输出：0，开始的时候就没有新鲜的橘子，因此返回0
solution = Solution()
print(solution.orangesRotting(grid))


